﻿using System.Collections.Generic;
namespace GX
{
	public class TrieTree
	{
        Dictionary<char, TrieNode> _rootMap = new Dictionary<char, TrieNode>();

        List<int> _startIndices = new List<int>();
        List<int> _lengths = new List<int>();
        int _numSkip=1;
        public int numSkip {
            get { return _numSkip; }
            set
            {
                if (value < 1)
                    _numSkip = 1;
                else
                    _numSkip = value;
            }
        }
        TrieNode GetRoot(char key, bool autoCreate)
        {
            TrieNode node = null;
            if (!_rootMap.TryGetValue(key,out node) && autoCreate)
            {
                node = new TrieNode(key);
                _rootMap[key] = node;
            }
            return node;
        }
        public void AddKeyword(string text)
        {
            var node = GetRoot(text[0],true);
            node.AddKeyword(text,0);
        }
        void AddMatch(int startIndex, int length)
        {
            _startIndices.Add(startIndex);
            _lengths.Add(length);
        }
        public void ResetMatch()
        {
            _startIndices.Clear();
            _lengths.Clear();
        }
        public int matchCount { get { return _startIndices.Count; } }
        
        public int GetMatchIndexAt(int index)
        {
            return _startIndices[index];
        }
        public int GetMatchLengthAt(int index)
        {
            return _lengths[index];
        }
        public bool Match(string text)
        {
            ResetMatch();
            if (string.IsNullOrEmpty(text))
                return false;
            int len = text.Length;
            for (int index = 0; index < len; )
            {
                index += MatchRoot(text,index);
            }
            return _startIndices.Count > 0;
        }
        /// <summary>
        /// 有匹配：结束于最后一个匹配串的位置
        /// 无匹配：结束于当前字符位置
        /// 接下来都是以当前位置的下一个位置开始匹配
        /// </summary>
        /// <param name="text"></param>
        /// <param name="startIndex"></param>
        /// <returns></returns>
        int MatchRoot(string text, int startIndex)
        {
            var root = GetRoot(text[startIndex], false);
            if (null == root) return 1;

            int endIndex = 0;

            int loop = text.Length;
            int count;
            TrieNode node = root;
            for (int i = startIndex; i < loop; )
            {
                if(node.isKeyword)
                    endIndex = i;

                node = FindNextNode(node, text, i, out count);

                if (null == node)
                    break;
                else
                    i += count;
            }
            int step = 1;
            if (endIndex > 0)
            {
                step = endIndex - startIndex + 1;
                _startIndices.Add(startIndex);
                _lengths.Add(step);
            }
            return step;
        }
        TrieNode FindNextNode(TrieNode node, string text, int index,out int step)
        {
            int count = numSkip;
            int leftCount = text.Length - index - 1;
            if (leftCount < count)
                count = leftCount;
            
            for (int i = 1; i <= count; ++i)
            {
                var child = node.GetChild(text[index+i]);
                if (null != child)
                {
                    step = i;
                    return child;
                }
            }
            step = 0;
            return null;
        }
	}	
}